package com.yun.algorithm.dynamicprogramming.leetcode;

import java.util.Arrays;

/*
    方法2：贪心算法加二分查找，没有实现
 */
public class E04Leetcode300 {

    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        int max=1;
        for (int i = 0; i < nums.length; i++) {
            dp[i]=1;
            for (int j = 0; j < i; j++) {
                if(nums[i]-nums[j]>0){
                    dp[i]=Integer.max(dp[i],dp[j]+1);
                    max=Integer.max(max,dp[i]);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return max;
    }

    public static void main(String[] args) {
        int[] nums=new int[]{4,10,4,3,8,9};
        new E04Leetcode300().lengthOfLIS(nums);
    }
}
